package com.lfg.leetcode.leetcode300;


import java.util.TreeSet;

public class No363maxSumSubmatrix {
    public static void main(String[] args) {
        int ret = maxSumSubmatrix(new int[][]{
                new int[]{5, -4, -3, 4},
                new int[]{-3, -4, 4, 5},
                new int[]{5, 1, 5, -4},
        }, 10);

        int ret2 = maxSumSubmatrix(new int[][]{
                new int[]{2, 2, -1},
        }, 0);
        System.out.println(ret);
        System.out.println(ret2);
    }

    public static int maxSumSubmatrix2(int[][] matrix, int k) {
        if (matrix.length == 0) {
            return -1;
        }
        int cnt = Integer.MIN_VALUE;
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] total = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int t = matrix[i][j];
                if (i > 0) {
                    t += total[i - 1][j];
                }
                if (j > 0) {
                    t += total[i][j - 1];
                }
                if (i > 0 && j > 0) {
                    t -= total[i - 1][j - 1];
                }
                total[i][j] = t;
                for (int a = 0; a <= i; a++) {
                    for (int b = 0; b <= j; b++) {
                        int sum = t;
                        if (a > 0) {
                            sum -= total[a - 1][j];
                        }
                        if (b > 0) {
                            sum -= total[i][b - 1];
                        }
                        if (a > 0 && b > 0) {
                            sum += total[a - 1][b - 1];
                        }
                        if (sum == k) {
                            return k;
                        } else if (sum > k) {
                            continue;
                        }
                        cnt = Math.max(cnt, sum);
                    }
                }
            }
        }
        return cnt;
    }


    public static int maxSumSubmatrix(int[][] matrix, int k) {
        if (null == matrix ||
                matrix.length == 0 ||
                null == matrix[0] ||
                matrix[0].length == 0)
            return 0;
        int row = matrix.length, col = matrix[0].length;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < col; i++) {
            int[] sum = new int[row];
            for (int j = i; j < col; j++) {
                for (int m = 0; m < row; m++) {
                    sum[m] += matrix[m][j];
                }
                max = Math.max(max, findMax(sum, k));
            }
        }
        return max;
    }

    public static int findMax(int[] sum, int k) {
        int cum = 0, max = Integer.MIN_VALUE;
        TreeSet<Integer> set = new TreeSet<>();
        for (int each : sum) {
            set.add(cum);
            cum += each;
            Integer ceil = set.ceiling(cum - k);
            if (ceil != null) {
                max = Math.max(max, cum - ceil);
            }
        }
        return max;
    }
}



